package tree.StructureTreeNode;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName BuildTree
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-28 10:13
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class BuildTree {
    /**
     * 根据一棵树的中序遍历与后序遍历构造二叉树。
     * <p>
     * 注意: 你可以假设树中没有重复的元素。
     */

    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    //inorder   9, 3, 15, 20, 7
    //postorder 9, 15, 7, 20, 3
    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) return null;

        //找到后续的最后一个节点
        int postEndNum = postorder[postEnd - 1];
        //根据后续的最后一个节点找到，中序的分节点的序号,根据这个序号分开为左边的树和右边的树
        Integer inNo = map.get(postEndNum);
        //根据中序的节点构造二叉树的主节点
        TreeNode root = new TreeNode(inorder[inNo]);
        int inLeft = inNo - inBegin;
        root.left = findNode(inorder, inBegin, inNo, postorder, postBegin, postBegin + inLeft);
        root.right = findNode(inorder, inNo + 1, inEnd, postorder, postBegin + inLeft, postEnd - 1);

        return root;
    }


    Map<Integer, Integer> map1 = new HashMap<>();

    //inorder   9, 3, 15, 20, 7
    //postorder 9, 15, 7, 20, 3
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map1.put(inorder[i], i);
        }
        return buildTreeNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildTreeNode(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart >= inEnd || postStart >= postEnd) return null;
        Integer inNum = map1.get(postorder[postEnd - 1]);

        Integer inLeft = inNum - inStart;

        TreeNode root = new TreeNode(inorder[inNum]);

        root.left = buildTreeNode(inorder, inStart, inNum, postorder, postStart, postStart + inLeft);
        root.right = buildTreeNode(inorder, inNum + 1, inEnd, postorder, postStart + inLeft, postEnd - 1);
        return root;
    }

    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();
        System.out.println(buildTree.buildTree1(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3}));
    }
}